Testing newly developed software is an essential part of the process of software product development. Software developers use a variety of techniques to test software for errors. The techniques that have developed for testing software have sprung from various schools of thought concerning how best to test software.
A first school of thought believes that software changes so much and so frequently that it is not worth automating the testing process at all. Accordingly, many different human software testers are hired to physically test the software. Often the software is tested at a “beta” test site; that is, the software developer enlists the aid of outside users to test the new software. The users, often under a nondisclosure agreement, use the new software and report on any errors found in the software. This is a long and difficult process because many person-years of testing are required to ensure that the new software has no errors. If only one or two beta test sites are used, the process consumes long periods of time because the small number of users are less likely to uncover errors than a large group of testers. As a result, software developers generally use a large number of beta test sites in order to reduce the time required for testing the software. Beta testing, however, is a costly process because of the large number of test sites involved. In addition, people tend to burn out. Further, this method is not the best one to use as the complexity of the software increases. Specifically, as the complexity of the software increases, it becomes more mathematically infeasible that human testers are going to find all or even a good number of the problems with the software.
A second school of thought believes that automated software testing is the preferred approach. This school has spawned many testing paradigms, some of which are discussed below.
A first approach involves using scripts of keystrokes and the like to test the software. That is, static automation scripts are used to exercise the same sequence of commands in the same order every time. These scripts, however, are costly to maintain when the software changes. And, although the tests are repeatable, since they always perform the same commands, they rarely find new bugs.
A second approach involves so-called “monkey testing.” In monkey testing, a program is written that defines a series of randomly selected actions that is then executed in connection with the software. Monkey testing can be difficult to use, particularly if you want to direct the testing to a particular part of an application. In addition, because “monkeys” do not understand the application, in their ignorance they can miss many bugs. An exemplary monkey testing approach is described in U.S. Pat. No. 5,513,315.
A third approach pertains to so-called model-based testing. Model-based testing does not record test sequences verbatim, like static test automation does, nor does it bang away at the keyboard blindly like monkey testing. Rather, model-based testing uses a description of the application's behavior to determine what actions are possible and what outcome is expected. This automation generates new test sequences endlessly, adapts well to changes in the application, can be run on many machines at once, and can run day and night.
Exploring model-based testing in somewhat more detail, the following example is given in which a behavioral model is created and used to test a software application. This example is also applicable to other types of models such as production grammars. Additional information can be found in Robinson, Intelligent Test Automation, Software Testing & Quality Engineering, Sep./Oct. 2000, Volume 2, Issue 5. The essence of model-based testing is to describe the application behavior that you expect in a way that can be used to generate tests. Two questions can be used for every action that you are going to test:                (1) When is an action possible; and        (2) What is the outcome when this action is executed?        
As an example, consider that you have been asked to test the behavior of files in a Window folder. In particular, you are going to test the Create, Delete, and Invert Selection actions. The first thing that is done is that the actions are modeled.
Modeling the “Create” Action
For simplicity, in this example and responsive to question (1) above, Create is only possible in this model when there are 0 files in the folder. Responsive to question (2), the outcome of the Create action is that when you create a file in a folder, the number of files in the folder increases by one. The newly created file is initially Selected, so it appears highlighted in the folder. In fact, the new file is the only Selected file in the folder, no matter how many were Selected before the Create action.
Modeling the “Delete” Action
Responsive to question (1) above, Delete is only possible in this model when there is at least 1 Selected File in the folder. Responsive to question (2) above, the outcome when Delete is executed is that any Selected file disappears from the folder.
Modeling the “Invert Selection” Action
Responsive to question (1) above, Invert Selection is always possible in this model, even when there are 0 Files in the folder. Responsive to question (2) above, the outcome of selecting Invert Selection is that all Selected files in the folder become Unselected, and all Unselected files become Selected. When there are 0 files in the folder, Invert Selection leaves the folder unchanged.
The State Model
With the above information having been defined, a state model can now be constructed that describes the software system's behavior. This technique can, however, work on other types of models as well.
FIG. 1 shows an exemplary state model 100 for the above described system. Model 100 incorporates all of the behaviors described above. Note the way that the Invert Selection action loops from the 0 Files state back to the 0 Files state. That models the way that Invert Selection does nothing if there is nothing to invert.
Now that an abstraction of the application's function has been derived, each of these actions could be manually tested to verify whether the implementation of the Windows folder behaves as expected. This could, however, take too much time and effort. A computer, however, is a logical choice for testing this system. The state model of FIG. 1 can be represented in a format known as a “state table” that the computer can read. Each row of the state table shows the Ending State that will result when an action is applied to the application in the Starting State. The state table effectively allows one to traverse the state space in which the state model is defined. Traversing the state space provides a sequence of test actions that can be performed on the software. As an example, consider the state table immediately below.
Starting StateActionEnding State0 FilesInvert Selection0 Files0 FilesCreate1 Selected File1 Selected FileInvert Selection1 Unselected File1 Selected FileDelete0 Files1 Unselected FileInvert Selection1 Selected File
Once the information in the state model has been placed into a state table that the computer can understand, the computer can be configured to test the behavior of the system. The computer uses the state table to generate sequences of tests to run against the application.
Random Walk Testing
One simple way to generate test actions is to randomly select any available action from the current state of the application. For example, if you are in the 0 Files Starting State, you can choose either of these two actions:                Invert Selection (which leaves you in the 0 Files State)        Create (which leaves you in the 1 Selected File State)        
By choosing random actions in this way, you can generate many unusual sequences and you may eventually exercise all of the actions in the model (for simple models). The issue for a random walk, however, concerns the efficiency of the algorithm. The random walk is very inefficient at reaching all actions given the limited time to for testing.
FIG. 2 shows an exemplary random walk. Notice that the random walk executes the same action (i.e. Invert Selection) four times in a row, but has so far left two other actions untouched. Such is the nature of random walk testing. That is, random walk testing tends to get stuck in localized portions of the state graph. Consider this problem in the context of a very large state space where the state model representing a particular software application or applications has a large number of nodes or states. The problem with using random walk testing in a very large state space is that the random walk tends to be very localized. Thus, achieving a high degree of traversal in the state model is very difficult if not impossible.
Chinese Postman Walk
As noted above, random walks are inefficient at reaching all test actions when the model is large. The problem becomes how to test all of the actions in the model efficiently. This turns out to be the same problem a letter carrier faces when delivering mail. Imagine that each of the actions in the model is a street where mail must be delivered—and that each of the states in the model is an intersection where the letter carrier can change directions. Just as the letter carrier must travel down each street to deliver the mail, we must test each action in the model. And in both cases, we would like to minimize the amount of additional travel needed.
A Chinese mathematician named Kwan Mei-Ko formulated an elegant solution to this problem, and it is known as the Chinese Postman algorithm in his honor. Kwan's method generates a path through the state model that exercises every action in the model in the fewest number of steps. The test sequence listed below covers all five actions in the model in only five steps. This efficiency can be handy if you have a large application that you want to test quickly.
Action to ExecuteEnding StateInvert Selection0 FilesCreate1 Selected FileInvert Selection1 Unselected FileInvert Selection1 Selected FileDelete0 Files
For more on Kwan's solution, the reader is directed to Kwan, M-K, “Graphic Programming Using Odd and Even Points”, Chinese Journal of Mathematics, Vol. 1(1962).
Some actions in a model, such as hitting Invert Selection with 0 Files in the folder—do not change the state of the application. If you think that bugs are more likely to occur where the application changes state, you may want to prioritize your efforts by first testing the state-changing actions. A simple way to do this is to filter out from the state table any actions that do not change the state. In the table immediately above, this would remove the first action (i.e. Invert Selection). The Chinese Postman solution in software testing is not the best choice because it does not permit exploration in the state space in a relatively uniform fashion, without resorting to an exhaustive approach of visiting every state.
Anti-Random Walk
The shortfalls of random walk testing gave rise to a paradigm called an “anti-random walk”. Anti-random walk algorithms essentially keep track of a history of where the algorithm has previously been (i.e. what past nodes in the state model have been tested), and makes a decision to traverse to a next node that is most different from the past nodes. The goal of the anti-random walk is to cover the “far corners” of the state space as efficiently as possible in the shortest amount of time. For example, in testing a specific piece of software that includes MS Word and Internet Explorer, an anti-random walk algorithm might open Word and go to a certain place within the application and store that history in a list. The anti-random walk algorithm would then select a place that is most different, e.g. Internet Explorer, and go there and take some actions (e.g. printing something), and store that history in the list.
In one anti-random walk approach, different “operational modes” are defined. As an example, consider the following operational modes:                Program Running        Program Not running        Main window        Help window        Font        Clock in analog mode        Clock in digital mode        
Given the various operational modes, it is then very easy to create a rule that is directed to identifying available states for testing (e.g. if Not_Running, then certain states are not available). This allows for implementation of an anti-random walk testing strategy quite easily. For example, if the present state is “Running.Main_Window.Analog”, then finding a state that is very different from this one is a matter of using the right algorithm (such as a Hamming distance algorithm) to produce “Running.Font.Digital”, where the Hamming distance in this example would be 2.
There are several problems with anti-random walk testing. First, anti-random walk testing is not a realistic representation of the way that people tend to use software. It is nice from the standpoint of enabling large trajectories across the state space that represents the software being tested, but it is still not realistic. Another problem with this approach is that it tends to be deterministic. By “deterministic” is meant that there is no randomness—i.e. everyone who implements the rules will get the same result. Because of its determinism, the approach can become stale and miss bugs in the software. Further, due to the very nature of the anti-random walk approach, the approach does not desirably “drift” or “diffuse”. That is, the approach is not well-suited for locally traversing the state space.
Against this backdrop, a continuing need for specific approaches for automated software testing remains unfulfilled. Accordingly, this invention arose out of concerns associated with providing improved methods and systems for automated software testing and modeling user behavior.